﻿/*
题目：飞机座位分配概率

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，

当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？

*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <list>
#include <numeric>

using namespace std;


class Solution {
public:
    // 1 / n 表示刚好选对了自己的位置
    // (n - 2) / n 表示不选自己的位置，同时不选第 n 个位置，这会导致某个乘客需要做出同样的选择
    // 这时候如果该乘客选择了第一个用户原来的位置，那么仍然可以让后面的乘客都做出正确的选择

    double nthPersonGetsNthSeat(int n) {
        // 每一位乘客都不能做到最后一位上
        if (n == 1)     return 1;

        // 选错位置，会导致下一个乘客也选错位置
        return (double)1 / n + (double)(n - 2) / n * nthPersonGetsNthSeat(n - 1);
    }
};